The display and transmission of visual images is increasingly important for modern communications. In particular, it is important for modern computer driven displays to receive, transmit, and display sequences of images in rapid succession such as is shown in movies. The quality of the visual display can be improved by representing the visual images in a digital format. Generally, a visual image can be represented by dividing the image into sufficiently small picture elements, called pixels, and assigning to each pixel a color and a value representing the intensity of the color for the pixel. For example, a typical 8 inch by 10 inch visual image may be divided into a two dimensional array of 768 by 1024 pixels wherein each pixel is further divided into 3 subpixels. The three subpixels are each associated with one of the three primary colors red, green, or blue. Each subpixel is assigned a digital value corresponding to the intensity level for the color the subpixel. The subpixels are small enough such that the human eye does not resolve each subpixel. Rather, the image presented by a pixel to the viewer is some combination of the three colors associated with each subpixel weighted by the intensity value for each subpixel color. As a result, a visual image is represented by three two dimensional matrices of color intensity values. This representation is commonly referred to as RGB (Red Green Blue) data for images.
The digital image represents a high quality image because the pixels are small. However, as the pixel gets smaller, there are more pixels for the same size image and more intensity values to store, manipulate, and transmit. The fact that more pixels requires more data also results in a reduction in the ability to transmit images because the amount of data for each image transmitted is so large. As a result, various efforts have been made to transform this RGB data into another form of data which can be transmitted and stored efficiently and which can also be re-transformed back into RGB data for display. The new form of data most often chosen relates the RGB data to a luminance value and two chrominance values. In particular, the luminance value represents the intensity of a pixel on a grey scale which provides an accurate representation of the image to a monochrome display. The luminance value is obtained by weighting each intensity value of the RGB data and combining them. For example, the National Television Systems Committee (NTSC) standard luminance value Y=0.299R+0.587G+0.114B, wherein R is the red intensity value, G is the green intensity value, and B is the blue intensity value. The two chrominance values convey information which describes how the colors differ from monochrome. For example, the NTSC values are U=Y-B and V=Y-R. The luminance and chrominance representation of image data is referred to as YUV data. The RGB to YUV transform compacts most of the visual intensity information into the luminance variable. This effect is similar to viewing a color image on a monochrome monitor in that the viewer understands a significant portion of the image but does not understand it all. This effect is useful for reducing the amount of data representing the image because the YUV data can be digitally filtered and coded such that much of the chrominance data, and some of the luminance data, can be discarded and replaced with code values which can be stored and transmitted more efficiently. There are a variety of techniques for performing the YUV filtering process, the most common of which is a Discrete Cosine Transform (DCT). The DCT replaces local blocks of YUV pixel data (such as 6.times.6 pixels or 8.times.8 pixels) with data generated from the YUV to DCT conversion performed on the YUV data. The resulting DCT data is very compact and can be easily stored or transmitted. The RGB to YUV and YUV to DCT conversions are largely, but not exactly invertible, so that the compact DCT data can be re-converted back into a very accurate representation of the digitized image even though the re-converted data is not exactly the same as the original digital image data.
The basic problem with this image conversion process is that even though digital data can be conveniently compacted, through the YUV and DCT conversions, each conversion requires several multiplications, additions and/or subtractions. This is a problem because each multiplication, addition or subtraction requires time for a computer processor to implement. Processing multiple operations for each pixel and processing thousands of pixels per image requires a significant amount of processor time. This amount of processor time is typically large enough to degrade the rate at which sequential images can be displayed. Degrading the display rate degrades the ability to display objects in motion. As a result, either the speed at which the processor multiplies must be increased or the conversion process must be changed to require fewer multiplication steps in order to implement high quality motion displays. One prior art attempt at increasing the speed of the multiplications is to replace the multiplication operations with look up tables. Look up tables may reduce the time required for multiplication operations which often are much slower than additions or subtractions because multiplications in the binary number system are typically a series of bit shift and add operations so that the time for each multiplication is a multiple of an add operation. Also, look-up tables are convenient to implement whereas special purpose multiplication hardware is much more complex than special purpose fixed point addition, subtraction and shift hardware. However, even though a look up table decreases the number of multiplication operations, the table itself is typically not very fast. Moreover, many computer processors are very efficient in using time between multiplications when performing many multiplications because of the pipelined structure of the processor. When look up tables are used in conjunction with computer processors, the pipelined structure can be disrupted and the overall efficiency of image processing is decreased even though the individual look up table operation is faster than the multiplication operation. Therefore, look up tables have not been very successful in increasing the speed of the image processing.
Beyond improving the speed of the multiplication operation, the prior art has also attempted to reduce the number of non-trivial multiplication steps required in the DCT conversions. A non-trivial multiplication is multiplication by a factor other than two. Multiplication by a factor of two is a shift operation in the binary system. Non-trivial multiplications have been reduced in the prior art by recognizing that the DCT equations contain a fixed constant which can be factored from the DCT equations and combined with another procedure in the DCT process. The problem with this technique is that although there is a reduction in the number of multiplication steps, the reduction is small. In particular, the common factor removed generally multiplies another non-trivial factor which does not reduce the number of multiplication processes.